package datastructure;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * 删除整数的ｋ个数字，获得删除最后的最小值
 *
 * @author lzy
 * @create 2019-11-19 下午2:42
 */
public class Chapter5_9 {

    public static void main(String[] args) {
        System.out.println(removeKDigitsV2("1593212", 3));
        System.out.println(removeKDigitsV2("30200", 1));
        System.out.println(removeKDigitsV2("10", 2));
        System.out.println(removeKDigitsV2("541270936", 3));
    }

    public static String removeKDigitsV2(String num, int k) {
        //新整数的长度＝原整数长度－ｋ
        int newLength = num.length() - k;
        //创建一个栈，用于接收所有数字
        char[] stack = new char[num.length()];
        int top = 0;
        for (int i = 0; i < num.length(); ++i) {
            //遍历当前数字
            char c = num.charAt(i);
            //当栈顶数字大于遍历到的当前数字时，栈顶数字出栈（相当于出栈）
            while (top > 0 && stack[top - 1] > c && k > 0) {
                top -= 1;
                k -= 1;
            }

            //遍历到的当前数字入栈
            stack[top++] = c;
        }

        //找到栈中第１个非零数字的位置，以此构建新的整数字符串
        int offset = 0;
        while (offset < newLength && stack[offset] == '0') {
            offset++;
        }

        return offset == newLength ? "0" : new String(stack, offset, newLength - offset);
    }

    public static String removeKDigits(String num, int k) {
        String numNew = num;
        for (int i = 0; i < k; i++) {
            boolean hasCut = false;
            //从左向右遍历，找到比自己右侧数字大的数字并删除
            for (int j = 0; j < numNew.length() - 1; j++) {
                if (numNew.charAt(j) > numNew.charAt(j + 1)) {
                    numNew = numNew.substring(0, j) + numNew.substring(j + 1, numNew.length());
                    hasCut = true;
                    break;
                }
            }

            //如果没有找到要删除的数字，则删除最后一个数字
            if (!hasCut) {
                numNew = numNew.substring(1, numNew.length());
            }
        }

        //如果整数的所有数字都比删除了，直接返回０
        if (numNew.length() == 0) {
            return "0";
        }

        return numNew;
    }

    /**
     * 删除开始的０字符
     *
     * @param number
     * @return
     */
    private static String removeZero(String number) {
        for (int i = 0; i < number.length() - 1; i++) {
            if ('0' != number.charAt(i)) {
                break;
            }

            number = number.substring(1, number.length());
        }

        return number;
    }
}
